{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "### 用静态数组构建动态数组"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DynamicArray:\n",
    "    max_size = 16\n",
    "    cur_size = 0\n",
    "    array = [None] * max_size\n",
    "    \n",
    "    def push_back(self, e):\n",
    "        if self.cur_size == self.max_size:\n",
    "            self.max_size *= 2\n",
    "            newArray = [None] * self.max_size\n",
    "            for i in range(self.cur_size):\n",
    "                newArray[i] = self.array[i]\n",
    "            self.array = newArray\n",
    "        self.array[self.cur_size] = e\n",
    "        self.cur_size += 1\n",
    "        \n",
    "    def pop_back(self):\n",
    "        if self.cur_size == 0:\n",
    "            return None\n",
    "        else:\n",
    "            self.cur_size -= 1\n",
    "            return self.array[self.cur_size]\n",
    "    \n",
    "    def size(self):\n",
    "        return self.cur_size\n",
    "    \n",
    "    def index(self, i):\n",
    "        return self.array[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "mylist = DynamicArray()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "mylist.push_back(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.index(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.pop_back()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "mylist.pop_back()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mylist.size()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 找数组左边的重复数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个数组，以从左往右的顺序，返回每一个数第一次出现的下标，如果不存在则输出-1\n",
    "\n",
    "例子：[1,3,1,2,1]\n",
    "\n",
    "输出：[-1,-1,0,-1,0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_duplicate(array):\n",
    "    index_dict = {}\n",
    "    result = []\n",
    "    for idx, value in enumerate(array):\n",
    "        if value in index_dict:\n",
    "            result.append(index_dict[value])\n",
    "        else:\n",
    "            result.append(-1)\n",
    "            index_dict[value] = idx\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 5 µs, sys: 0 ns, total: 5 µs\n",
      "Wall time: 7.87 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[-1, -1, 0, -1, 0]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time find_duplicate([1,3,1,2,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "875 ns ± 36.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit find_duplicate([1,3,1,2,1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 238. 除自身以外数组的乘积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。\n",
    "\n",
    "示例:\n",
    "\n",
    "输入: [1,2,3,4]\n",
    "输出: [24,12,8,6]\n",
    "说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。\n",
    "\n",
    "进阶：\n",
    "你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def array_product(nums):\n",
    "    length = len(nums)\n",
    "    left, right = [1], [1]\n",
    "    for i in range(length - 1):\n",
    "        left.append(left[-1] * nums[i])\n",
    "        right.append(right[-1] * nums[length - 1 - i])\n",
    "    return [left[i] * right[length - 1 - i] for i in range(length)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 7 µs, sys: 0 ns, total: 7 µs\n",
      "Wall time: 9.78 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[120, 60, 40, 30, 24]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time array_product([1,2,3,4,5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.36 µs ± 132 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit array_product([1,2,3,4,5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 时间复杂度O(n^2)\n",
    "def array_product2(nums):\n",
    "    length = len(nums)\n",
    "    result = [1] * length\n",
    "    for i in range(length):\n",
    "        for j in range(length):\n",
    "            if i != j:\n",
    "                result[i] *= nums[j]\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 9 µs, sys: 0 ns, total: 9 µs\n",
      "Wall time: 11 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[120, 60, 40, 30, 24]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time array_product2([1,2,3,4,5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.5 µs ± 142 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit array_product2([1,2,3,4,5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 时间复杂度O(n)，空间复杂度O(1)\n",
    "def array_product3(nums):\n",
    "    length = len(nums)\n",
    "    result = [None] * length\n",
    "    result[0] = nums[0]\n",
    "    for i in range(1, length - 1):\n",
    "        result[i] = result[i - 1] * nums[i]\n",
    "    temp = 1\n",
    "    for i in reversed(range(1, length)):\n",
    "        result[i] = temp * result[i - 1]\n",
    "        temp *= nums[i]\n",
    "    result[0] = temp\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 7 µs, sys: 0 ns, total: 7 µs\n",
      "Wall time: 8.82 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[120, 60, 40, 30, 24]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time array_product3([1,2,3,4,5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.49 µs ± 22.6 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit array_product3([1,2,3,4,5])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "思考题：有n个询问，每个询问给出数组下标范围[i,j]，要求返回[i,j]之间所有数的乘积。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ranged_array_product(nums, inquiry):\n",
    "    length = len(nums)\n",
    "    idxes = [None] * length\n",
    "    for i in range(length):\n",
    "        idxes[i] = []\n",
    "    \n",
    "    for i, (left, right) in enumerate(inquiry):\n",
    "        for j in range(left, right):\n",
    "            idxes[j].append(i)\n",
    "    \n",
    "    result = [1] * (len(inquiry))\n",
    "    for i in range(length):\n",
    "        for j in idxes[i]:\n",
    "            result[j] *= nums[i]\n",
    "\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 8 µs, sys: 0 ns, total: 8 µs\n",
      "Wall time: 10 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[12, 20]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time ranged_array_product([2,3,4,5], [[1,3], [2,4]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 1. 两数之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。\n",
    "\n",
    "你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。\n",
    "\n",
    "示例:\n",
    "\n",
    "给定 nums = [2, 7, 11, 15], target = 9\n",
    "\n",
    "因为 nums[0] + nums[1] = 2 + 7 = 9\n",
    "所以返回 [0, 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 两遍Hash\n",
    "def two_sum(nums, target):\n",
    "    num_dict = {}\n",
    "    for i, item in enumerate(nums):\n",
    "        num_dict[item] = i\n",
    "    \n",
    "    for i, item in enumerate(nums):\n",
    "        b = target - item\n",
    "        if b in num_dict and num_dict[b] != i:\n",
    "            return [i, num_dict[b]]\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 4 µs, sys: 0 ns, total: 4 µs\n",
      "Wall time: 5.96 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[0, 1]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time two_sum([2, 7, 11, 15], 9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "792 ns ± 35.6 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit two_sum([2, 7, 11, 15], 9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 4 µs, sys: 0 ns, total: 4 µs\n",
      "Wall time: 5.96 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[0, 1]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time two_sum([3, 3, 11, 15], 6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 一遍Hash\n",
    "def two_sum2(nums, target):\n",
    "    num_dict = {}\n",
    "    for i, item in enumerate(nums):\n",
    "        b = target - item\n",
    "        if b in num_dict and num_dict[b] != i:\n",
    "            return [i, num_dict[b]]\n",
    "        num_dict[item] = i\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 4 µs, sys: 0 ns, total: 4 µs\n",
      "Wall time: 6.68 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[1, 0]"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time two_sum2([2, 7, 11, 15], 9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "512 ns ± 14.7 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit two_sum2([2, 7, 11, 15], 9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 3 µs, sys: 0 ns, total: 3 µs\n",
      "Wall time: 5.96 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[1, 0]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time two_sum2([3, 3, 11, 15], 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 189. 旋转数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。\n",
    "\n",
    "示例 1:\n",
    "\n",
    "输入: [1,2,3,4,5,6,7] 和 k = 3\n",
    "输出: [5,6,7,1,2,3,4]\n",
    "解释:\n",
    "向右旋转 1 步: [7,1,2,3,4,5,6]\n",
    "向右旋转 2 步: [6,7,1,2,3,4,5]\n",
    "向右旋转 3 步: [5,6,7,1,2,3,4]\n",
    "\n",
    "示例 2:\n",
    "\n",
    "输入: [-1,-100,3,99] 和 k = 2\n",
    "输出: [3,99,-1,-100]\n",
    "解释: \n",
    "向右旋转 1 步: [99,-1,-100,3]\n",
    "向右旋转 2 步: [3,99,-1,-100]\n",
    "\n",
    "说明:\n",
    "\n",
    "尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。\n",
    "要求使用空间复杂度为 O(1) 的原地算法。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "# length次交换\n",
    "def move1(nums, k):\n",
    "    assert k >= 0, 'Error: Negative Step'\n",
    "    length = len(nums)\n",
    "    idx = 0\n",
    "    temp = nums[idx]\n",
    "    while True:\n",
    "        idx = (idx + k) % length\n",
    "        nums[idx], temp = temp, nums[idx]\n",
    "        if idx == 0:\n",
    "            break\n",
    "    return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 4 µs, sys: 0 ns, total: 4 µs\n",
      "Wall time: 6.2 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[5, 6, 7, 1, 2, 3, 4]"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time move1( [1,2,3,4,5,6,7], 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "811 ns ± 20.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit move1( [1,2,3,4,5,6,7], 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 3次翻转\n",
    "def move2(nums, k):\n",
    "    assert k >= 0, 'Error: Negative Step'\n",
    "    a = len(nums) - k\n",
    "    nums[:a] = nums[:a][::-1]\n",
    "    nums[a:] = nums[a:][::-1]\n",
    "    nums = nums[::-1]\n",
    "    return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 4 µs, sys: 0 ns, total: 4 µs\n",
      "Wall time: 5.25 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[5, 6, 7, 1, 2, 3, 4]"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time move2( [1,2,3,4,5,6,7], 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "662 ns ± 19.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit move2( [1,2,3,4,5,6,7], 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "# k次平移\n",
    "def move3(nums, k):\n",
    "    assert k >= 0, 'Error: Negative Step'\n",
    "    for i in range(k):\n",
    "        nums.insert(0, nums.pop())\n",
    "    return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 13 µs, sys: 1 µs, total: 14 µs\n",
      "Wall time: 16 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[5, 6, 7, 1, 2, 3, 4]"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time move3( [1,2,3,4,5,6,7], 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.54 µs ± 6.51 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit move3( [1,2,3,4,5,6,7], 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 697. 数组的度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。\n",
    "\n",
    "你的任务是找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。\n",
    "\n",
    "示例 1:\n",
    "\n",
    "输入: [1, 2, 2, 3, 1]\n",
    "输出: 2\n",
    "\n",
    "解释: \n",
    "输入数组的度是2，因为元素1和2的出现频数最大，均为2.\n",
    "连续子数组里面拥有相同度的有如下所示:\n",
    "[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]\n",
    "最短连续子数组[2, 2]的长度为2，所以返回2.\n",
    "\n",
    "示例 2:\n",
    "\n",
    "输入: [1,2,2,3,1,4,2]\n",
    "输出: 6\n",
    "\n",
    "注意:\n",
    "\n",
    "nums.length 在1到50,000区间范围内。\n",
    "nums[i] 是一个在0到49,999范围内的整数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 使用散列表存储每个元素的(出现次数，起始下标，终止下标)\n",
    "def find_shortest_sub_array(nums):\n",
    "    num_dict = {}\n",
    "    max_element = 0\n",
    "    max_count = 0\n",
    "    for idx, element in enumerate(nums):\n",
    "        if element in num_dict:\n",
    "            count, left, _ = num_dict[element]\n",
    "            new_count = count + 1\n",
    "            num_dict[element] = new_count, left, idx\n",
    "        else:\n",
    "            new_count = 1\n",
    "            num_dict[element] = new_count, idx, idx\n",
    "        if new_count > max_count:\n",
    "            max_element = element\n",
    "            max_count = new_count\n",
    "    _, left, right = num_dict[max_element]\n",
    "    return right + 1 - left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 3 µs, sys: 1e+03 ns, total: 4 µs\n",
      "Wall time: 4.77 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time find_shortest_sub_array([2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 5 µs, sys: 1 µs, total: 6 µs\n",
      "Wall time: 6.91 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time find_shortest_sub_array([1, 2, 2, 3, 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 5 µs, sys: 0 ns, total: 5 µs\n",
      "Wall time: 8.11 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time find_shortest_sub_array([1,2,2,3,1,4,2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.21 µs ± 3.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit find_shortest_sub_array([1,2,2,3,1,4,2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 849. 到最近的人的最大距离"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在一排座位（ seats）中，1 代表有人坐在座位上，0 代表座位上是空的。\n",
    "\n",
    "至少有一个空座位，且至少有一人坐在座位上。\n",
    "\n",
    "亚历克斯希望坐在一个能够使他与离他最近的人之间的距离达到最大化的座位上。\n",
    "\n",
    "返回他到离他最近的人的最大距离。\n",
    "\n",
    "示例 1：\n",
    "\n",
    "输入：[1,0,0,0,1,0,1]\n",
    "输出：2\n",
    "\n",
    "解释：\n",
    "如果亚历克斯坐在第二个空位（seats[2]）上，他到离他最近的人的距离为 2 。\n",
    "如果亚历克斯坐在其它任何一个空位上，他到离他最近的人的距离为 1 。\n",
    "因此，他到离他最近的人的最大距离是 2 。 \n",
    "示例 2：\n",
    "\n",
    "输入：[1,0,0,0]\n",
    "输出：3\n",
    "\n",
    "解释： \n",
    "如果亚历克斯坐在最后一个座位上，他离最近的人有 3 个座位远。\n",
    "这是可能的最大距离，所以答案是 3 。\n",
    "\n",
    "提示：\n",
    "\n",
    "1 <= seats.length <= 20000\n",
    "seats 中只含有 0 和 1，至少有一个 0，且至少有一个 1。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "def max_dist_to_closest(seats):\n",
    "    max_space = 0\n",
    "    idx = 0\n",
    "    left_space = 0\n",
    "    right_space = 0\n",
    "    while True:\n",
    "        all_zero = True\n",
    "        for i in range(max_space + 1):\n",
    "            if seats[idx + max_space - i] == 1:\n",
    "                idx = idx + max_space - i + 1\n",
    "                all_zero = False\n",
    "                break\n",
    "                \n",
    "        if all_zero:\n",
    "            max_space += 1\n",
    "            idx += max_space\n",
    "            if idx >= len(seats):\n",
    "                return max_space\n",
    "            while seats[idx] == 0:\n",
    "                idx += 1\n",
    "                max_space += 1\n",
    "                if idx >= len(seats):\n",
    "                    return max_space\n",
    "        \n",
    "        if idx == max_space:\n",
    "            left_space = max_space\n",
    "        \n",
    "        if idx + max_space >= len(seats):\n",
    "            break\n",
    "    \n",
    "    for i in range(max_space):\n",
    "        if seats[len(seats) - 1 - i] == 1:\n",
    "            break\n",
    "        right_space += 1\n",
    "    \n",
    "    return max(left_space, right_space, (max_space - 1) // 2 + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max_dist_to_closest([1,0,0,0,1,0,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max_dist_to_closest([1,0,0,0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.97 µs ± 37.4 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit max_dist_to_closest([0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 右遍历+左遍历\n",
    "def max_dist_to_closest2(seats):\n",
    "    length = len(seats)\n",
    "    right_dist = [None] * length\n",
    "    \n",
    "    dist = float('inf')\n",
    "    for idx in reversed(range(length)):\n",
    "        if seats[idx] == 1:\n",
    "            dist = 1\n",
    "        else:\n",
    "            right_dist[idx] = dist\n",
    "            dist += 1\n",
    "    \n",
    "    max_dist = 0\n",
    "    dist = float('inf')\n",
    "    for idx in range(length):\n",
    "        if seats[idx] == 1:\n",
    "            dist = 1\n",
    "        else:\n",
    "            new_dist = min(dist, right_dist[idx])\n",
    "            if new_dist > max_dist:\n",
    "                max_dist = new_dist\n",
    "            dist += 1\n",
    "            \n",
    "    return max_dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max_dist_to_closest2([1,0,0,0,1,0,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max_dist_to_closest2([1,0,0,0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6.69 µs ± 97.7 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit max_dist_to_closest2([0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 遍历一次，左端和右端dist保持不变，中间dist = (dist - 1) // 2 + 1\n",
    "def max_dist_to_closest3(seats):\n",
    "    length = len(seats)\n",
    "    dist = 0\n",
    "    max_dist = 0\n",
    "    for i in range(length):\n",
    "        if seats[i] == 1:\n",
    "            if i != dist:\n",
    "                dist = (dist - 1) // 2 + 1\n",
    "            if dist > max_dist:\n",
    "                max_dist = dist\n",
    "            dist = 0\n",
    "        else:\n",
    "            dist += 1\n",
    "    if dist > max_dist:\n",
    "        max_dist = dist\n",
    "    return max_dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max_dist_to_closest3([1,0,0,0,1,0,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max_dist_to_closest3([0,0,0,1,0,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.68 µs ± 5.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit max_dist_to_closest3([0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0])"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}